class Solution:
    def isValid(self, s: str) -> bool:
        stack1 = []
        input_str =  ["(", "[", "{"]
        map = {")":"(", "]":"[", "}":"{"}

        for c in s:
            if c in input_str:
                stack1.append(c)
            else:
                if len(stack1)==0:
                    return False
                if map[c] == stack1[-1]:
                    stack1.pop()
                else:
                    return False
        return len(stack1)==0